module cl {
	export class SortedArray {
		public data : any[];
		private cb : (a, b) => boolean;
		private cbThis : Object;

		public constructor(cb : (a, b) => boolean, cbThis : Object) {
			this.data = [];
			this.cb = cb;
			this.cbThis = cbThis;
		}

		public refresh(o : any) : number {
			this.findAndRemove(o);
			return this.insert(o);
		}

		public findAndRemove(o : any) : void {
			let pos = this.data.indexOf(o);
			if (pos >= 0) {
				this.data.splice(pos, 1);
			}
		}

		public insert(o : any) : number {
			if (this.data.length == 0) {
				this.data.push(o);
				return 0;
			}

			let small = 0;
			let big = this.data.length - 1;

			if (this.cb.call(this.cbThis, o, this.data[small])) {
				this.data.splice(small, 0, o);
				return small;
			}
			if (this.cb.call(this.cbThis, this.data[big], o)) {
				this.data.splice(big + 1, 0, o);
				return big + 1;
			}

			return this.insertBetween(o, small, big);
		}

		private insertBetween(o : any, small : number, big : number) : number {
			if (big - small < 2) {
				this.data.splice(big, 0, o);
				return big;
			}
			let mid = Math.floor((small + big) / 2);
			let lt = this.cb.call(this.cbThis, o, this.data[mid]);
			let gt = this.cb.call(this.cbThis, this.data[mid], o);
			if (!gt && !lt) {
				this.data.splice(mid, 0, o);
				return mid;
			}
			return lt // o < mid
				? this.insertBetween(o, small, mid)
				: this.insertBetween(o, mid, big);
		}
	}

	export class SortedSet {
		public data : any[];
		private cb : (a, b) => boolean;
		private cbThis : Object;

		public constructor(cb : (a, b) => boolean, cbThis : Object) {
			this.data = [];
			this.cb = cb;
			this.cbThis = cbThis;
		}

		public insert(o : any) : number {
			if (this.data.length == 0) {
				this.data.push(o);
				return 0;
			}

			let small = 0;
			let big = this.data.length - 1;

			if (this.cb.call(this.cbThis, o, this.data[small])) {
				let tag = this.cb.call(this.cbThis, this.data[small], o) ? 1 : 0;
				this.data.splice(small, tag, o);
				return small;
			}
			if (this.cb.call(this.cbThis, this.data[big], o)) {
				let tag = this.cb.call(this.cbThis, o, this.data[big]) ? 1 : 0;
				this.data.splice(big + (1 - tag), tag, o);
				return big + (1 - tag);
			}

			return this.insertBetween(o, small, big);
		}

		private insertBetween(o : any, small : number, big : number) : number {
			if (big - small < 2) {
				this.data.splice(big, 0, o);
				return big;
			}

			let mid = Math.floor((small + big) / 2);

			if (this.cb.call(this.cbThis, o, this.data[mid])) {
				if (this.cb.call(this.cbThis, this.data[mid], o)) {
					this.data.splice(mid, 1, o);
					return mid;
				} else {
					return this.insertBetween(o, small, mid);
				}
			} else {
				return this.insertBetween(o, mid, big);
			}
		}
	}
}